class Solution {
    int ret;
    int[] tmp;
    public int reversePairs(int[] record) {
        tmp = new int[record.length];
        merge(record, 0, record.length - 1);
        return ret;
    }
    public void merge(int[] record, int left, int right) {
        if(left >= right) return;
        int mid = (left + right) / 2;

        merge(record, left, mid);
        merge(record, mid + 1, right);

        int s1 = left, e1 = mid, s2 = mid + 1, e2 = right, i = 0;
        while(s1 <= e1 && s2 <= e2) {
            if(record[s1] <= record[s2]) {
                tmp[i++] = record[s1++];
            }else {
                //找出该数之前，有多少个数比我大
                ret += (e1 - s1 + 1);
                tmp[i++] = record[s2++];
            }
        }
        while(s1 <= e1) tmp[i++] = record[s1++];
        while(s2 <= e2) tmp[i++] = record[s2++];

        for(int k = left; k <= right; k++) {
            record[k] = tmp[k - left];
        }
    }
}